from copy import copy

class Entry:
  def __init__(self, value, refcount=1):
    self.value=value
    self.refcount=refcount

  def __hash__(self):
    return self.value.__hash__()

  def inc(self):
    self.refcount=self.refcount+1

  def dec(self):
    self.refcount=self.refcount-1

  def __str__(self):
    return 'Entry('+str(self.refcount)+':'+str(self.value)+')'

  def __repr__(self):
    return self.__str__()

# A shadowing, clonable, copy-on-write map
class MagicMap:
  def __init__(self, map=None, mmap=None):
    if map:
      self.map={}
      for key in map:
        value=map[key]
        self.put(key, value)
    elif mmap:
      self.map=copy(mmap)
    else:
      self.map={}

  def __hash__(self):
    return tuple(self.map.keys()).__hash__()

  def keys(self):
    return self.map.keys()

  def __del__(self):
    for key in self.map:
      entry=self.map[key]
      entry.dec()

  def __getitem__(self, key):
    return self.get(key)

  def get(self, key):
    print(key, self.map.keys())
    entry=self.map[key]
    return entry.value

  def resolve(self, keys):
    return self.resolveFrom(keys, 0)

  def resolveFrom(self, keys, index):
    #print 'resolveFrom:', keys, keys[index], self.map
    if len(keys)==index+1:
      #print '1!'
      return self.get(keys[index])
    else:
      #print '2@'
      key=keys[index]
      entry=self.map[key]
      map=entry.value
      #print 'recursing', keys[index+1], map
      return map.resolveFrom(keys, index+1)

  def __setitem__(self, key, value):
    self.put(key, value)

  def put(self, key, value):
    #print 'put', key, value
    if type(value)==dict:
      value=MagicMap(map=value)
    elif type(value)==list:
      value=MagicList(lst=value)
    #print 'value', value

    try:
      entry=self.map[key]
      #print 'refcount:', entry.refcount
      if entry.refcount==0: # already freed, replace
        self.map[key]=Entry(value)
      elif entry.refcount==1: # modify in place
        entry.value=value
      else: # split off
        entry.dec()
        self.map[key]=Entry(value)
    except KeyError:
      self.map[key]=Entry(value)

  def puts(self, keys, value):
    self.putsFrom(keys, value, 0)

  def puts(self, keys, value, index):
    if len(keys)==index+1:
      self.put(keys[index], value)
    else:
      key=keys[index]
      entry=self.map[key]
      map=entry.value
      if entry.refcount==0: # already freed
        return
      elif entry.refcount==1: # modify in place
        map.putsFrom(keys, value, index+1)
      else: # split off
        entry.dec()
        map=map.clone()
        self.map[key]=Entry(map)
        map.putsFrom(keys, value, index+1)

  def remove(self, key):
    try:
      entry=self.map[key]
    except:
      return
    if entry.refcount==0: # already freed, remove
      del self.map[key]
    elif entry.refcount==1: # only reference, remove
      del self.map[key]
    else: # shared reference, decrement refcount
      entry.dec()
      del self.map[key]

  def removes(self, keys):
    self.removesFrom(keys, 0)

  def removesFrom(self, keys, index):
    if len(keys)==index+1:
      self.remove(keys[index])
    else:
      key=keys[index]
      entry=self.map[key]
      map=entry.value
      if entry.refcount==0: # already freed
        return
      elif entry.refcount==1: # modify in place
        map.removesFrom(keys, index+1)
      else: # split off
        entry.dec()
        map=map.clone()
        self.map[key]=Entry(map)
        map.removesFrom(keys, index+1)

  def clone(self):
    for key in self.map:
      entry=self.map[key]
      entry.inc()
    return MagicMap(mmap=self.map)

  def __str__(self):
    s='~{'
    for key in self.map:
      s=s+str(key)+': '
      entry=self.map[key]
      s=s+str(entry.value)+', '
    if len(self.map.keys())>1:
      s=s[:-2]
    s=s+'}'
    return s

# A shadowing, clonable, copy-on-write list
class MagicList:
  def __init__(self, lst=None, mlist=None):
    if lst:
      self.list=[]
      for value in lst:
        self.append(value)
    elif mlist:
      self.list=copy(mlist.list)
    else:
      self.list=[]

  def __hash__(self):
    return tuple(self.list).__hash__()

  def __len__(self):
    return len(self.list)

  def __del__(self):
    for entry in self.list:
      entry.dec()

  def __getitem__(self, index):
    return self.get(index)

  def get(self, index):
    #print 'get', index, self.list
    entry=self.list[index]
    #print 'val', entry, entry.value, type(entry), entry.__class__
    return entry.value

  def __setitem__(self, index, value):
    #print 'insert', index, value
    if type(value)==dict:
      value=MagicMap(map=value)
    elif type(value)==list:
      value=MagicList(lst=value)

    entry=self.list[index]
    if entry.refcount<=1: # modify in place
      entry.value=value
    else: # split off
      entry.dec()
      self.list[index]=Entry(value)

  def insert(self, index, value):
    #print 'insert', index, value
    if type(value)==dict:
      value=MagicMap(map=value)
    elif type(value)==list:
      value=MagicList(lst=value)

    try:
      impact=0
      for x in range(index, len(self.list)):
        entry=self.list[x]
        if entry.refcount>1: # already freed, replace
          impact=impact+1
      if impact==0: # modify in place
        self.list.insert(index, Entry(value))
      else: # split off
        self.list.insert(index, Entry(value))
        for x in range(index+1, len(self.list)):
          entry=self.list[index]
          entry.dec()
          self.list[index]=Entry(entry.value)
    except IndexError:
      self.list[index]=Entry(value)

  def append(self, value):
    #print 'append', value, type(value)
    if type(value)==dict:
      value=MagicMap(map=value)
    elif type(value)==list:
      value=MagicList(lst=value)
    self.list.append(Entry(value))

  def __delitem__(self, index):
    self.delete(index)

  def resolve(self, keys):
    return self.resolveFrom(keys, 0)

  def resolveFrom(self, keys, index):
    #print 'resolveFrom:', keys, keys[index], self.list
    if len(keys)==index+1:
      return self.get(keys[index])
    else:
      key=keys[index]
      list=self.get(key)
      return list.resolveFrom(keys, index+1)

  def clone(self):
    for entry in self.list:
      entry.inc()
    return MagicList(mlist=self)

  def __str__(self):
    s='~['
    for entry in self.list:
      value=entry.value
      s=s+str(value)+', '
    if len(self.list)>1:
      s=s[:-2]
    s=s+']'
    return s

  def __repr__(self):
    return self.__str__()

if __name__=='__main__':
  m=MagicMap()
  m.put('a', 'b')
  m.put('c', 'd')

  n=m.clone()
  n.put('e', 'f')
  n.put('c', 'd2')

  m.put('a', 'b2')

  o=n.clone()
  o.remove('a')

  print m, n, o

  print '-----------'

  m=MagicMap()
  m2=MagicMap()
  m3=MagicMap()

  m.put('a', m2)
  m.put('b', m3)

  m2.put('c', 'd')
  m3.put('e', 'f')

  n=m.clone()

  m.remove('a')
  n.remove('b')

  print m, n

  print '-----------'

  m=MagicMap()
  m2=MagicMap()
  m3=MagicMap()

  m.put('a', m2)
  m.put('b', m3)

  m2.put('c', 'd')
  m3.put('e', 'f')

  n=m.clone()

  m.puts(['a', 'c'], 'd2')
  n.removes(['b', 'e'])
  n.puts(['b', 'f'], 'g')

  o=MagicMap()

  print m, n, o

  print '-----------'

  l=MagicList()
  l.append('a')
  l.append('b')
  l.append('c')
  l.append('d')

  m=l.clone()

  l.append('e')
  m.append('f')

  print l, m

  l.insert(0, 'a2')
  m.insert(1, 'b2')

  print l, m

  del l[1]
  del m[0]

  print l, m

  l2=MagicList()
  m2=MagicList()

  l2.append('q')
  l2.append('r')
  m2.append('w')
  m2.append('x')

  l.append(l2)
  m.append(m2)

  print l, m

  print '-----------------'

  l.appends([5], 't')
  m.appends([5], 'y')

  print l, m

  l.inserts([5, 0], 'q2')
  m.inserts([5, 1], 'w2')

  print l, m

  l.deletes([5, 1])
  m.deletes([5, 0])

  print l, m

